Packet classification operations are frequently performed in high performance routers to determine how packets received at an input of a router are classified. This classification typically determines both an output port to which a packet should be sent and also determines what, if any, special handling the packet should receive. Typical packet classification operations utilize packet filters. Such filters may specify values of source and destination address fields of an IP header, a protocol field and source and destination port numbers, for example. Conventional packet classification operations have frequently utilized only a limited number of packet filters, which makes it possible to match every incoming packet against a predefined and ordered sequence of filters. Unfortunately, these conventional packet classification operations typically do not scale efficiently to systems having high packet processing rates and/or large packet filtering requirements.
Ternary content addressable memories (TCAMs) support packet processing operations by enabling comparisons to be performed in parallel between an applied search key (e.g., packet or field within a packet) and a plurality of stored data patterns (i.e., CAM entries), which are typically configured as a plurality of value and bit mask pairs within a corresponding plurality of TCAM cells. However, the typical drawbacks of TCAMs are relatively high power consumption and relatively inefficient representation of filters containing ranges to be matched. Such filters are typically handled by using multiple TCAM entries for each stored data pattern having at least one field therein that specifies a range to be matched. But, representing each data pattern using multiple TCAM entries can reduce the effective capacity of a TCAM by a factor of two or typically much greater than two in most applications. These shortcomings associated with TCAMs are more fully described in an article by Ed Spitznagel et al., entitled “Packet Classification Using Extended TCAMs,” Proceedings of the 11th IEEE International Conference on Network Protocols (2003). As described in this article, one way to better handle filters when performing packet processing is to expand TCAM functionality to directly incorporate range check circuits within a TCAM core. These range check circuits are also described in a technical report by Ed Spitznagel, entitled “CMOS Implementation of a Range Check Circuit,” Washington University, Report No. WUCSE-2004-39 (2004). In particular, this report describes storing lower and upper bounds for each range to be matched and using dedicated range check circuitry, which performs a comparison using a set of stages. Techniques for performing range matching are also disclosed in U.S. Pat. No. 6,742,105 to Ott, entitled “Method and System for Range Matching;” and U.S. Pat. No. 6,766,317 to Sharma et al., entitled “Range Check Cell and a Method for The Use Thereof.”